package com.mengfou.linklist;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 将链表划分为三个部分，大于number、等于number和小于number
 * @author mengfou
 * 2022-1-8
 */
public class ListPartitionDemo {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 5, 4, 8, 3, 1, 4};
        Node linkedList = Node.createLinkedList(arr);
        Node.printLinkedList(linkedList);

        Node node = new ListPartitionDemo().partitionList_3(linkedList, 3);
        Node.printLinkedList(node);
    }

    /**
     * 更节省空间的做法
     * @param list 链表
     * @param number 划分数据
     * @return 划分后的链表
     */
    public Node partitionList_3(Node list, int number) {
        if (list == null || list.next == null) return list;
        Node leftPartStart = new Node(-1);
        Node leftPartEnd = new Node(-1);
        leftPartStart.next = leftPartEnd;
        leftPartEnd.next = null;
        Node midPartStart = new Node(-1);
        Node midPartEnd = new Node(-1);
        midPartStart.next = midPartEnd;
        midPartEnd.next = null;
        Node rightPartStart = new Node(-1);
        Node rightPartEnd = new Node(-1);
        rightPartStart.next = rightPartEnd;
        rightPartEnd.next = null;
        Node ptr = list, leftP = leftPartStart, midP = midPartStart, rightP = rightPartStart;
        while(ptr != null){
            Node temp = ptr.next;
            if(ptr.val < number){
                ptr.next = leftP.next;
                leftP.next = ptr;
                leftP = leftP.next;
            } else if(ptr.val == number){
                ptr.next = midP.next;
                midP.next = ptr;
                midP = midP.next;
            }else{
                ptr.next = rightP.next;
                rightP.next = ptr;
                rightP = rightP.next;
            }
            ptr = temp;
        }
        if(midPartStart.next != midPartEnd){
            leftP.next = midPartStart.next;
        }
        if(rightPartStart.next != rightPartEnd){
            midP.next = rightPartStart.next;
        }
        rightP.next = null;
        return leftPartStart.next;
    }


    public Node partitionList_2(Node list, int number){
        if(list == null || list.next == null) return list;
        Node leftPartStart = new Node(-1);
        leftPartStart.next = null;
        Node midPartStart = new Node(-1);
        midPartStart.next = null;
        Node rightPartStart = new Node(-1);
        rightPartStart.next = null;
        Node ptr = list;
        while(ptr != null){
            Node temp = ptr.next;
            if(ptr.val < number){
                ptr.next = leftPartStart.next;
                leftPartStart.next = ptr;
            } else if(ptr.val > number){
                ptr.next = rightPartStart.next;
                rightPartStart.next = ptr;
            } else{
                ptr.next = midPartStart.next;
                midPartStart.next = ptr;
            }
            ptr = temp;
        }
        Node temp = leftPartStart.next;
        while(temp!= null && temp.next != null){
            temp = temp.next;
        }
        Node midTemp = midPartStart.next;
        while(midTemp != null && midTemp.next != null){
            midTemp = midTemp.next;
        }
        if(temp != null){
            temp.next = midPartStart.next;
        }
        if(midTemp != null){
            midTemp.next = rightPartStart.next;
        }
        return leftPartStart.next;
    }


    /**
     * 划分链表为三个部分，小于、等于和大于
     * @param list 链表
     * @param number 比较数字
     * @return 链表
     */
    public Node partitionList_1(Node list, int number){
        if(list == null || list.next == null) return list;
        List<Node> datas = new ArrayList<>();
        Node ptr = list;
        while(ptr != null){
            datas.add(ptr);
            ptr = ptr.next;
        }
        Node[] objects = new Node[datas.size()];
        for (int i = 0; i < datas.size(); i++) {
            objects[i] = datas.get(i);
        }

        int left = 0, right = objects.length - 1, k = 0;
        while(k <= right){
            if(objects[k].val < number){
                swap(objects, left, k);
                if(left == k) k++;
                left++;
            } else if(objects[k].val > number){
                swap(objects, right, k);
                right--;
            }else{
                k++;
            }
        }

        Node dummyNode = new Node(-1);
        ptr = dummyNode;
        for (Node object : objects) {
            ptr.next = object;
            ptr = ptr.next;
        }
        ptr.next = null;
        return dummyNode.next;
    }

    private void swap(Node[] objects, int left, int i) {
        Node temp = objects[left];
        objects[left] = objects[i];
        objects[i] = temp;
    }


}
